﻿#pragma once	
#include <assert.h>
#include <iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK
};


template<class T>
struct RBTreeNode
{

	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Colour _col;


	RBTreeNode(const T& T)
		:_data(T)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};


template<class T>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T> Self;


	Node* _node;
	RBTreeIterator(Node* node)
		:_node(node)
	{}


	Self& operator++()
	{
		assert(_node);
		Node* cur = _node;
		Node* sonR = _node->_right;
		if (sonR)
		{
			_node = _node->_right;
			return *this;
		}
		Node* parent = _node->_parent;
		while (parent)
		{
			if (cur == parent->_left)
			{

				_node = parent;
				return *this;
			}
			else
			{
				cur = parent;
				parent = parent->_parent;
			}
		}
		_node = parent;
		return *this;

	}

	
	Self operator++(int)
	{
		assert(_node);
		Node* ret = _node;

		Node* cur = _node;
		Node* sonR = _node->_right;
		if (sonR)
		{
			_node = _node->_right;
			return ret;
		}
		Node* parent = _node->_parent;
		while (parent)
		{
			if (cur == parent->_left)
			{

				_node = parent;
				return ret;
			}
			else
			{
				cur = parent;
				parent = parent->_parent;
			}
		}
		_node = parent;
		return ret;

	}

	Self& operator--()
	{
		assert(_node);
		Node* cur = _node;
		Node* sonL = _node->_left;
		if (sonL)
		{
			_node = _node->_left;
			return *this;
		}
		Node* parent = _node->_parent;
		while (parent)
		{
			if (cur == parent->_right)
			{

				_node = parent;
				return *this;
			}
			else
			{
				cur = parent;
				parent = parent->_parent;
			}
		}
		_node = parent;
		return *this;

	}

	Self operator--(int)
	{
		assert(_node);
		Node* ret = _node;

		Node* cur = _node;
		Node* sonL = _node->_left;
		if (sonL)
		{
			_node = _node->_left;
			return *this;
		}
		Node* parent = _node->_parent;
		while (parent)
		{
			if (cur == parent->_right)
			{

				_node = parent;
				return *this;
			}
			else
			{
				cur = parent;
				parent = parent->_parent;
			}
		}
		_node = parent;
		return ret;

	}

	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &_node->_data;
	}


	bool operator!=(const Self& s)const
	{
		return _node != s._node;

	}
	bool operator==(const Self& s)const
	{
		return _node == s._node;
	}
};




//template<class K, class V>
template<class K, class T, class KeyofT>

class RBTree
{
	//typedef RBTreeNode<K, V> Node;
	typedef RBTreeNode<T> Node;

public:
	typedef RBTreeIterator<T>  iterator;
	typedef RBTreeIterator<const T>  const_iterator;

	iterator begin()
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return cur;
	}
	iterator end()
	{
		return nullptr;
	}

	const_iterator begin() const
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return cur;
	}
	const_iterator end() const
	{
		return nullptr;
	}


	//iterator rbegin()
	//{
	//	Node* cur = _root;
	//	while (cur->_right)
	//	{
	//		cur = cur->_right;
	//	}
	//	return cur;
	//}
	//iterator rend()
	//{
	//	return nullptr;
	//}



	iterator find(const T& data)
	{
		Node* father = nullptr;
		Node* cur = _root;
		while (cur)
		{
			father = cur;
			if (kot(data) < kot(cur->_data))
			{
				cur = cur->_left;
			}
			else if (kot(data) > kot(cur->_data))
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}


	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}

	pair<iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			Node* newnode = new Node(data);
			newnode->_col = BLACK;
			_root = newnode;
			return { _root,true};
		}
		
		Node* father = nullptr;
		Node* cur = _root;
		while (cur)
		{
			father = cur;
			if (kot(data) < kot(cur->_data))
			{
				cur = cur->_left;
			}
			else if (kot(data) > kot(cur->_data))
			{
				cur = cur->_right;
			}
			else
			{
				return {cur,false };
			}
		}
		Node* newnode = new Node(data);
		cur = newnode;
		cur->_col = RED;
		if (kot(cur->_data) < kot(father->_data))
		{
			father->_left = cur;
			cur->_parent = father;
		}
		else
		{
			father->_right = cur;
			cur->_parent = father;
		}


		//更新红黑
		while (father && father->_col == RED)
		{

			Node* grandfather = father->_parent;


			if (father == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况1 变色
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					uncle->_col = father->_col = BLACK;

					cur = grandfather;
					father = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)//情况2：旋转
				{
					//单旋
					if (cur == father->_left)
					{
						//右旋;
						RotateR(grandfather);
						father->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (cur == father->_right)//双旋
					{
						//左右双旋;
						RotateLR(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;

					}

					break;
				}


			}
			else if (father == grandfather->_right)
			{
				Node* uncle = grandfather->_left;
				//情况1 变色
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					uncle->_col = father->_col = BLACK;

					cur = grandfather;
					father = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)//情况2：旋转
				{
					//单旋
					if (cur == father->_right)
					{
						//左旋;
						RotateL(grandfather);
						father->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (cur == father->_left)
					{
						RotateRL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}
			}

		}
		_root->_col = BLACK;
		return {newnode, true };
	}


	// 右单旋

	void RotateR(Node* parent)
	{
		Node* father = parent;
		Node* sonL = father->_left;
		// 1. 先把 sonL 挪到 father 的位置
		sonL->_parent = father->_parent;
		if (father->_parent)
		{
			if (father == father->_parent->_left)
			{

				father->_parent->_left = sonL;
			}
			else
			{
				father->_parent->_right = sonL;

			}
		}
		else
		{
			_root = sonL;
		}

		// 2. 调整 father
		father->_parent = sonL;
		father->_left = sonL->_right;

		if (sonL->_right)
			sonL->_right->_parent = father;

		sonL->_right = father;

	}

	// 左单旋
	void RotateL(Node* parent)
	{
		Node* father = parent;
		Node* sonR = father->_right;

		sonR->_parent = father->_parent;
		if (father->_parent)
		{
			if (father == father->_parent->_left)
			{
				father->_parent->_left = sonR;
			}
			else
			{
				father->_parent->_right = sonR;

			}
		}
		else
		{
			_root = sonR;
		}

		father->_parent = sonR;
		father->_right = sonR->_left;

		if (sonR->_left)
			sonR->_left->_parent = father;

		sonR->_left = father;


	}
	// 右左双旋
	void RotateRL(Node* parent)
	{


		Node* sonR = parent->_right;
		Node* sonRL = sonR->_left;

		RotateR(sonR);
		RotateL(parent);


	}
	// 左右双旋
	void RotateLR(Node* parent)
	{


		Node* sonL = parent->_left;
		Node* sonLR = sonL->_right;

		RotateL(sonL);
		RotateR(parent);

	}


	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
private:
	Node* _root = nullptr;
	KeyofT kot;
};